@InProceedings{AndradeNetoGued:2005:LiAlEx,
author = "Andrade Neto, Pedro Ribeiro de and Guedes, Andr{\'e} Luiz Pires",
affiliation = "{Federal University of Paran{\'a}}",
title = "A linear algorithm for exact pattern matching in planar
subdivisions",
booktitle = "Proceedings...",
year = "2005",
editor = "Rodrigues, Maria Andr{\'e}ia Formico and Frery, Alejandro
C{\'e}sar",
organization = "Brazilian Symposium on Computer Graphics and Image Processing, 18.
(SIBGRAPI)",
publisher = "IEEE Computer Society",
address = "Los Alamitos",
keywords = "sub-isomorphism, planar subdivisions.",
abstract = "Graph sub-isomorphism is a very common approach to solving pattern
search problems, but this is a NP-complete problem. This way, it
is necessary to invest in research of approximate solutions, or in
special cases of the problem. Planar subdivisions can be
considered as a special case of graphs, because, in addition to
nodes and edges, there is a more rigid topology in relation to the
order of the edges, arising to the concept of face. This work
presents a linear algorithm for pattern search in planar
subdivisions. The presented algorithm is based on a hybrid
approach between the dual and the region adjacency graph (RAG) to
represent the patterns, saving any additional storage cost. Thus,
the patterns are looked over the search subdivision, using a
region growing algorithm.",
conference-location = "Natal, RN, Brazil",
conference-year = "9-12 Oct. 2005",
doi = "10.1109/SIBGRAPI.2005.5",
url = "http://dx.doi.org/10.1109/SIBGRAPI.2005.5",
language = "en",
ibi = "6qtX3pFwXQZeBBx/GHBVm",
url = "http://urlib.net/ibi/6qtX3pFwXQZeBBx/GHBVm",
targetfile = "andradep_matchsubdivisions.pdf",
urlaccessdate = "2024, May 03"
}